package com.qfedu.entity.course10;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * 邻接表实现
 */
public class AdListGraph {
    Map<String, Vertex> vertexsMap; //存储所有的顶点

    AdListGraph() {
        this.vertexsMap = new HashMap<>();
    }

    public static void main(String[] args) {
        AdListGraph graph = new AdListGraph();
        graph.insertVertex("A");
        graph.insertVertex("B");
        graph.insertVertex("C");
        graph.insertVertex("D");
        graph.insertVertex("E");
        graph.insertVertex("F");
        graph.insertEdge("C", "A", 1);
        graph.insertEdge("F", "C", 2);
        graph.insertEdge("A", "B", 4);
        graph.insertEdge("E", "B", 2);
        graph.insertEdge("A", "D", 5);
        graph.insertEdge("D", "F", 4);
        graph.insertEdge("D", "E", 3);
        graph.print();
    }

    public void insertVertex(String vertexName) {
        //添加顶点
        Vertex vertex = new Vertex(vertexName, null);
        vertexsMap.put(vertexName, vertex);
    }

    public void insertEdge(String begin, String end, int weight) {
        //添 加弧
        Vertex beginVertex = vertexsMap.get(begin);
        if (beginVertex == null) {
            beginVertex = new Vertex(begin, null);
            vertexsMap.put(begin, beginVertex);
        }
        Edge edge = new Edge(end, weight, null);
        if (beginVertex.next == null) {
            beginVertex.next = edge;
        } else {
            Edge lastEdge = beginVertex.next;
            while (lastEdge.next != null) {
                lastEdge = lastEdge.next;
            }
            lastEdge.next = edge;
        }
    }


    public void print() { //打印图
        Set<Map.Entry<String, Vertex>> set = vertexsMap.entrySet();
        Iterator<Map.Entry<String, Vertex>> iterator = set.iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Vertex> entry = iterator.next();
            Vertex vertex = entry.getValue();
            Edge edge = vertex.next;
            while (edge != null) {
                System.out.println(vertex.name + " 指向 " + edge.name + " 权值 为：" + edge.weight);
                edge = edge.next;
            }
        }
    }

    /*** 顶点 */
    public class Vertex {
        String name; //顶点名称
        Edge next; //从该定点出发的边

        public Vertex(String name, Edge next) {
            this.name = name;
            this.next = next;
        }
    }

    /*** 边 */
    public class Edge {
        String name; //被指向的顶点
        int weight; //弧的权值
        Edge next; //被指向的下一个边

        public Edge(String name, int weight, Edge next) {
            this.name = name;
            this.weight = weight;
            this.next = next;
        }
    }
}